package com.company.tree;

import com.company.arrays.ArrayPrinter;

import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;

public class TraverseTree {




    /**
     * 前序遍历
     * pre Traverse
     */
    public void preTraverse(TreeNode root) {
        result.clear();
        preTraverse11(root, result);
        printList();
    }

    private void printList() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("[");
        for (TreeNode node : result) {
            stringBuilder.append(node.val);
            stringBuilder.append(",");
        }
        stringBuilder.append("]");
        System.out.println(stringBuilder.toString());
    }


    private List<TreeNode> result = new ArrayList<>();

    /**
     * 递归的方式进行前序遍历
     */
    private void preTraverse11(TreeNode root, List<TreeNode> results) {
        if (root == null) {
            return;
        }

        results.add(root);
        preTraverse11(root.left, results);
        preTraverse11(root.right, results);

    }

    private List<Integer> preTraverse1(TreeNode root) {
        List<Integer> arr = new ArrayList<>();

        TreeNode node = root;
        while (true) {


        }

    }

    /**
     * 中序遍历 递归的方式
     * pre Traverse
     */
    private void midTraverse(TreeNode root, List<TreeNode> results) {
        if (root == null) {
            return;
        }
        midTraverse(root.left, results);
        results.add(root);
        midTraverse(root.right, results);
    }

    public void midTraverse(TreeNode root) {
        result.clear();
        midTraverse(root, result);
        printList();
    }


    /**
     * 前序遍历
     * pre Traverse
     */
    public void postTraverse(TreeNode root) {
        result.clear();
        postTraverse(root, result);
        printList();
    }

    private void postTraverse(TreeNode root, List<TreeNode> results) {
        if (root == null) {
            return;
        }

        postTraverse(root.left, results);
        postTraverse(root.right, results);
        results.add(root);
    }

    public void levelTraverse(TreeNode root) {
        result.clear();
        Queue<TreeNode> queue = new LinkedBlockingQueue<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            result.add(node);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }

        printList();

    }

    public void levelZTraverse(TreeNode root) {
        result.clear();

        Queue<TreeNode> queue = new LinkedBlockingQueue<>();
        Stack<TreeNode> stack = new Stack<>();

        Queue<TreeNode> levelQueue=new LinkedBlockingQueue<>();

        queue.add(root);
        while (!queue.isEmpty() || !stack.isEmpty()) {

            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                result.add(node);
                if (node.left != null) {
                    levelQueue.add(node.left);
                }
                if (node.right != null) {
                    levelQueue.add(node.right);
                }
                continue;
            }
            
            while (!levelQueue.isEmpty()){
                TreeNode node = levelQueue.poll();
                stack.push(node);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            while (!stack.isEmpty()){
                result.add(stack.pop());
            }

        }

        printList();
    }
    /**
     * 后续 遍历  使用stack 构成 递归
     *
     * 遍历的基本单元是   3个元素的 树  首先 要看是否
     *
     * */
    public List<Integer> postTraverseByLoop(TreeNode root){
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        stack.push(root);
        while (!stack.isEmpty()){
            while (node.left!=null){
                stack.push(node.left);
                node = stack.peek();
            }
            node = stack.pop();
            result.add(node.val);
            //访问右子树  将 右子树 看成是root
            if (node.right != null) {
                stack.push(node.right);
                node = node.right;
            }
            //回到开始状态 看成是 递归操作
        }
        System.out.println(result);
        return result;
    }

    /**
     * 中序 遍历  使用stack 构成 递归
     * */
    public List<Integer> inTraverseByLoop(TreeNode root){
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        stack.push(root);
        while (!stack.isEmpty()){
            //移动到左侧叶子节点
            while (node.left!=null){
                node = stack.peek();
                stack.push(node.left);
            }
            //当前子树下  左子节点 为null 访问当前节点
            TreeNode pop = stack.pop();
            result.add(pop.val);
            //访问右子节点  递归操作  将右子节点当做root
            if (pop.right != null) {
                stack.push(pop.right);
            }

        }
        System.out.println(result);
        return result;
    }
    /**
     * 先序 遍历  使用stack 构成 递归
     * */
    public List<Integer> preTraverseByLoop(TreeNode root){
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode node = root;
        stack.push(root);
        while (!stack.isEmpty()){
            node = stack.pop();
            result.add(node.val);

            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        System.out.println(result);
        return result;
    }

}
